An associative database stores data in two basic types of items: entity instances and relation instances. Each entity instance has a unique identifier, a name, and a type. Entity instances are discrete items that have independent existence. In contrast, each relation instance is a “link” or “association” that specifies other items. Each relation instance includes a unique identifier, a source identifier, a verb identifier, and a target identifier. Source identifiers, verb identifiers, and target identifiers of relations specify the identifiers of entity instances. Thus, relations describe associations between items. For the purpose of clarity, associative database items are set forth in a fixed-width font. Names of entity instances are preceded by the “$” sign. Furthermore, names of entity instances used as verb items are set forth herein in an italicized fixed-width font. For example, entity instance “1” may have the name “$ cat”, entity instance “2” may have the name “$ sat on”, and entity instance “3” may have the name “$ mat”. Arelation instance having identifier “10” may specify “1” as the source identifier, “2” as the verb identifier, and “3” as the target identifier. Thus, relation “10” may describe the relation “(cat sat on mat)”.
An associative database may describe more sophisticated associations by allowing identifiers of relation instances to be source or target identifiers. Continuing the previous example, entity instance “4” may have the name “$ is colored” and entity instance “5” may have the name “$ red”. Arelation instance having identifier “11” may specify “3” as a source identifier, “4” as the verb identifier, and “5” as the target identifier. Thus, relation instance “11” may describe the relation “(mat is colored red)” Now, if relation instance “10” specified “1” as the source identifier, “2” as the verb identifier, and “11” as the target identifier, relation instance “10” would describe the association, “(cat sat on (mat is colored red)).” This relation describes the idea that a cat sat on a mat that is colored red. By building such associations, an associative database may store any type of information.